import java.util.List;

/**
 * @author LKQ
 * @date 2022/2/28 14:50
 * @description 单链表
 */
public class ListNode {
    int val;
    ListNode next;
    ListNode prev;

    public ListNode() {
    }

    public ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
    public ListNode(int val, ListNode prev, ListNode next) {
        this.val = val;
        this.prev = prev;
        this.next = next;
    }

    /**
     * 利用双指针升序合并两个升序链表
     * @param l1 升序 l1
     * @param l2 升序 l2
     * @return 升序 l
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode prev = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }
        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 == null ? l2 : l1;
        return dummy.next;
    }

    /**
     * 迭代法实现链表的反转
     * @param head 链表的头节点
     * @return 反转后的链表
     */
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            // 创建下一个节点，
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    /**
     * 利用快慢指针寻找链表的中点
     * @param head head
     * @param tail tail
     * @return middle
     */
    public ListNode getMiddleNode(ListNode head, ListNode tail) {
        ListNode slow = head, fast = head;
        while (fast != tail) {
            slow = slow.next;
            fast = fast.next;
            if (fast != tail) {
                fast = fast.next;
            }
        }
        return slow;
    }
}

/**
 * 利用链表实现循环双端队列
 */
class MyCircularDeque {
    /**
     * 队列大小
     */
    int size;
    /**
     * 队列容量
     */
    int capacity;
    ListNode head;
    ListNode tail;
    public MyCircularDeque(int k) {
        size = 0;
        capacity = k;
        // 虚拟头节点和虚拟尾节点
        head = new ListNode();
        tail = new ListNode();
        head.next = tail;
        tail.prev = head;
    }

    /**
     * 将一个节点添加到双端队列头部。
     * @param node node
     */
    public void addToHead(ListNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    /**
     * 将一个节点添加到双端队列尾部
     * @param node node
     */
    public void addToTail(ListNode node) {
        node.prev = tail.prev;
        node.next = tail;
        tail.prev.next = node;
        tail.prev = node;
    }

    public boolean insertFront(int value) {
        ListNode node = new ListNode(value);
        if (size < capacity) {
            addToHead(node);
            size++;
            return true;
        }
        return false;
    }

    public boolean insertLast(int value) {
        ListNode node = new ListNode(value);
        if (size < capacity) {
            addToTail(node);
            size++;
            return true;
        }
        return false;
    }

    public boolean deleteFront() {
        if (size >= 1) {
            head.next.next.prev = head;
            head.next = head.next.next;
            size--;
            return true;
        }
        return false;
    }

    public boolean deleteLast() {
        if (size >= 1) {
            tail.prev.prev.next = tail;
            tail.prev = tail.prev.prev;
            size--;
            return true;
        }
        return false;
    }

    public int getFront() {
        return size == 0 ? -1 : head.next.val;
    }

    public int getRear() {
        return size == 0 ? -1 : tail.prev.val;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == capacity;
    }
}




